题目分析
汉诺塔是一个经典的递归算法,小伙伴们在学习算法课程时应该接触过这个问题。当时我学习递归的时候,遇到的两个经典问题,一个是斐波那契数列问题,一个就是汉诺塔问题。当然这个问题难度稍微大了一些,当时只需要打印移动的过程,这个题目是要用数组模拟移动的过程。
递归
思考一个问题,如果要将A通过B移动到C,我们应该怎么做?类比于将大象放进冰箱需要几步?
- 将A中除了最后一个盘子,其他的盘子都放在B中。
- 将A中最后一个盘子放入C。
- 将B中所有盘子放入C。
定义:subQuestion(A, B, C, nums)指将A中的nums个盘子在B柱子的帮助下,全部放入到C中。
因此递归的思路就很明确了,**先将A中的盘子除了最后一个,在C的帮助下都放入B,可以表示为subQuestion(A, C, B, nums - 1)。然后将A中剩余的盘子放入C,C.push_back(A.back()),A.pop_back()。最后将B中的所有盘子,在A的帮助下都放入C,此时B中盘子个数为nums - 1,可以表示为subQuestion(B, A, C, nums - 1)**。
其中出口条件是nums = 0时,当nums = 0,不需要任何操作,直接return即可。
算法的**时间复杂度为$O(2^n)$,空间复杂度为$O(n)$**。
其中每次操作都会分裂为两个额外的操作,因此时间复杂度为$O(2^n)$,空间复杂度是递归的栈调用消耗的空间,其中递归的深度最大为n,空间复杂度为$O(n)$
1 | #include<iostream> |
刷题总结
这个问题时最经典的递归问题,没有接触过的小伙伴可能觉得有些困难,理清楚思想之后还是比较清晰的,希望小伙伴们可以顺利写出来。